package 动态规划.递归参数思考型;

public class 买卖股票的最佳时机4 {
	/**
	 * 这道题，很简单了，
	 * 股票 3
	 * 是最多交易 2次， 
	 * 这个题 只不过 把 参数 counts  cong 2  变成 了 k 而已！ 
	 */
	
	public int recursion(int index,int counts,int status,int prices[],int len) {
		if(counts == 0 || index == len)
			return 0;
		
		int ans = 0,ans1 = 0;
		
		if(status == 0) {
			ans = recursion(index + 1,counts,status,prices,len);
			ans1 = recursion(index + 1,counts,1,prices,len) - prices[index];
		}
		else {
			ans = recursion(index + 1,counts,status,prices,len);
			ans1 = recursion(index + 1,counts - 1,0,prices,len) + prices[index];
			
		}
		return Math.max(ans, ans1);
		
	}
	public int dp(int prices[],int k) {
		int len = prices.length;
		int dp[][][] = new int [len + 1][k + 1][2];
		for(int index = len - 1;index >= 0;index--) {
			for(int count = 1;count <= k;count++) {
				dp[index][count][0] = Math.max(dp[index + 1][count][0], dp[index + 1][count][1] - prices[index]);
				dp[index][count][1] = Math.max(dp[index + 1][count][1] ,dp[index + 1][count -1][0] + prices[index]);
			}
		}
		
		return dp[0][k][0];
	}
	
}

